import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */
/**
 * 题目：对称二叉树
 * 思路一：递归判断左右子树的对应位置是否是相同
 * 思路二：通过层序遍历判断二叉树的每一层的节点值是否回文
 */

public class Test {
    public boolean isSymmetric(TreeNode root) {
        // 比较根结点的左子树和右子树
        return invertTree(root.left, root.right);
    }

    // 就是比较对应结点的值是否一样
    public boolean invertTree(TreeNode left, TreeNode right) {
        if (left != null && right == null || left == null && right != null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) {
            return false;
        }
        return invertTree(left.left, right.right) && invertTree(left.right, right.left);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
